package array;

import java.util.Arrays;

/**
 * @Classname : ShortestUnsortedContinuousSubarray
 * @Description : 581. 最短无序连续子数组
 * https://leetcode.cn/problems/shortest-unsorted-continuous-subarray/
 * @Author : cty
 * @Date 2023/4/18 23:28
 */


public class ShortestUnsortedContinuousSubarray {

    /**
     * 方法一：原数组与排序数组比对
     * @param nums
     * @return
     */
    public int findUnsortedSubarray(int[] nums) {
        // 复制数组并排序
        int[] array = nums.clone();
        Arrays.sort(array);
        // 从左遍历至第一个不相同的位置即为左边界
        int l = 0, r = nums.length - 1;
        while(l <= r && nums[l] == array[l]) {
            l++;
        }
        // 从右遍历至第一个不相同的位置即为右边界
        while(r >= l && nums[r] == array[r]) {
            r--;
        }
        return Math.max(r - l + 1, 0);
    }


    /**
     * 方法二：根据边界特征一次遍历
     * @param nums
     * @return
     */
    public int findUnsortedSubarray2(int[] nums) {
        int n = nums.length;
        if (n < 2) return 0;
        int min = Integer.MAX_VALUE, l = n - 1;
        int max = Integer.MIN_VALUE, r = 0;

        for (int i = 0; i < n; i++) {
            // 记录不满足 nums[p] >= max[0, p]的位置，即为右边界
            if (nums[i] < max) r = i;
                // 记录区间[0, p]的最大值
            else max = nums[i];

            // 记录不满足 nums[p] <= min[p, n-1]的位置，即为左边界
            if (nums[n - 1 - i] > min) l = n - 1 - i;
                // 记录区间[n-1-i, n-1]的最小值
            else min = nums[n - 1 - i];
        }
        return Math.max(r - l + 1, 0);
    }

}
